#include <iostream>
using namespace std;

const int MAX = 100;

struct Node
{
	int data;
	Node* lchild;
	Node* rchild;
};

class BinSortTree
{
public:
	BinSortTree(int a[]);
	~BinSortTree();
	void InsertBST(Node*& root, Node* s);
	Node* SearchBST(Node* root, int x);
	void DeleteBST(Node* parent, Node* child);
	int CountNode(Node* root);
	Node* FindParent(Node* root, int x);
	int Depth(Node* root);
	void AvgSeaLenOfSuccess();
	void AvgSeaLenOfFailure();
	void PreOrder(Node* root);
	void InOrder(Node* root);
	void PostOrder(Node* root);
	Node* BSTroot;
};

BinSortTree::BinSortTree(int a[])
{
	BSTroot = NULL;
	int i = 0;
	while (a[i])
	{
		Node* p = new Node;
		p->data = a[i];
		p->lchild = p->rchild = NULL;
		InsertBST(BSTroot, p);
		i++;
	}
}

void BinSortTree::InsertBST(Node*& root, Node* s)
{
	if (!root)
	{
		root = s;
	}
	else if (s->data < root->data)
	{
		InsertBST(root->lchild, s);
	}
	else
	{
		InsertBST(root->rchild, s);
	}
}

Node* BinSortTree::SearchBST(Node* root, int x)
{
	if (!root)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}
	else if (root->data > x)
	{
		return SearchBST(root->lchild, x);
	}
	else
	{
		return SearchBST(root->rchild, x);
	}
}

void BinSortTree::DeleteBST(Node* parent, Node* child)
{
	if (!child->lchild && !child->rchild)//child为叶子结点
	{
		if (parent->lchild == child)
		{
			parent->lchild = NULL;
		}
		else
		{
			parent->rchild = NULL;
		}
		delete child;
	}
	else if (!child->rchild)//child只有左子树
	{
		if (parent->lchild == child)
		{
			parent->lchild = child->lchild;
		}
		else
		{
			parent->rchild = child->lchild;
		}
		delete child;
	}
	else if (!child->lchild)//child只有右子树
	{
		if (parent->lchild == child)
		{
			parent->lchild = child->rchild;
		}
		else
		{
			parent->rchild = child->rchild;
		}
		delete child;
	}
	else//child左右子树皆不为空
	{
		Node* childTmp = child;
		Node* p = child->rchild;
		//寻找最左下结点
		while (p->lchild)
		{
			childTmp = p;
			p = p->lchild;
		}
		child->data = p->data;
		if (childTmp == child)
		{
			childTmp->rchild = p->rchild;
		}
		else
		{
			childTmp->lchild = p->lchild;
		}
		delete p;
	}
}

int BinSortTree::CountNode(Node* root)
{
	if (!root)
	{
		return 0;
	}
	else
	{
		int cl = CountNode(root->lchild);
		int cr = CountNode(root->rchild);
		return cl + cr + 1;
	}
}

Node* BinSortTree::FindParent(Node* root, int x)
{
	//无当前结点
	if (!root)
	{
		return NULL;
	}

	//当前结点存储数据x
	if (root->data == x)
	{
		return NULL;
	}
	else if (root->data > x)
	{
		if (!root->lchild)//当前结点无左子树
		{
			return NULL;
		}

		if (root->lchild->data == x)
		{
			return root;
		}
		else
		{
			return FindParent(root->lchild, x);
		}
	}
	else
	{
		if (!root->rchild)//当前结点无右子树
		{
			return NULL;
		}

		if (root->rchild->data == x)
		{
			return root;
		}
		else
		{
			return FindParent(root->rchild, x);
		}
	}
}

int BinSortTree::Depth(Node* root)
{
	if (!root)
	{
		return 0;
	}
	else
	{
		int hl = Depth(root->lchild);
		int hr = Depth(root->rchild);
		return (hl > hr ? hl : hr) + 1;
	}
}

//查找成功的平均查找长度为：∑（本层高度*本层元素个数）/节点总数
void BinSortTree::AvgSeaLenOfSuccess()
{
	if (!BSTroot)
	{
		cout << "0" << endl;
	}
	else
	{

	}
}

//查找不成功的平均查找长度：∑（本层高度*本层补上的叶子个数）/补上的叶子总数
void BinSortTree::AvgSeaLenOfFailure()
{

}

void BinSortTree::PreOrder(Node* root)
{
	if (!root)
	{
		return;
	}
	else
	{
		cout << root->data << " ";
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

void BinSortTree::InOrder(Node* root)
{
	if (!root)
	{
		return;
	}
	else
	{
		InOrder(root->lchild);
		cout << root->data << " ";
		InOrder(root->rchild);
	}
}

void BinSortTree::PostOrder(Node* root)
{
	if (!root)
	{
		return;
	}
	else
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		cout << root->data << " ";
	}
}

BinSortTree::~BinSortTree()
{
	if (BSTroot)
	{
		while (BSTroot->lchild)
		{
			DeleteBST(BSTroot, BSTroot->lchild);
		}
		while (BSTroot->rchild)
		{
			DeleteBST(BSTroot, BSTroot->rchild);
		}
		delete BSTroot;
	}
}

int main()
{
	int n;
	cout << "请输入要创建二叉排序树的组数：";
	cin >> n;
	cout << endl;

	int** a = new int* [n];
	if (!a)
	{
		cout << "内存申请错误！" << endl;
		return 1;
	}

	int i;
	for (i = 0; i < n; i++)
	{
		a[i] = new int[MAX];
		if (!a[i])
		{
			cout << "内存申请错误！" << endl;
			return 1;
		}

		cout << "请输入第" << i + 1 << "组的数据（0作结束标志）：";
		int j = -1;
		do
		{
			j++;
			cin >> a[i][j];
		} while (a[i][j]);
	}

	for (i = 0; i < n; i++)
	{
		cout << endl << "第" << i + 1 << "组二叉排序树：" << endl;
		BinSortTree BST(a[i]);

		cout << "\t深度为：";
		cout << BST.Depth(BST.BSTroot);
		cout << endl;

		cout << "\t前序遍历为：";
		BST.PreOrder(BST.BSTroot);
		cout << endl;

		cout << "\t中序遍历为：";
		BST.InOrder(BST.BSTroot);
		cout << endl;

		cout << "\t后序遍历为：";
		BST.PostOrder(BST.BSTroot);
		cout << endl;

		cout << "\t结点个数为：";
		cout << BST.CountNode(BST.BSTroot);
		cout << endl;

		int x;
		Node* p;
		cout << "\t请输入要查找的结点值：";
		cin >> x;

		cout << "\t其结点为：";
		p= BST.SearchBST(BST.BSTroot, x);
		if (!p)
		{
			cout << "未查找到";
		}
		else
		{
			cout << p << " " << p->data;
		}
		cout << endl;

		cout << "\t其父结点为：";
		p = BST.FindParent(BST.BSTroot, x);
		if (!p)
		{
			cout << "未查找到";
		}
		else
		{
			cout << p << " " << p->data;
		}
		cout << endl;
	}

	for (i = 0; i < n; i++)
	{
		delete[] a[i];
	}
	delete[] a;

	system("pause");
	return 0;
}